package queue;

public class MyLinkedListQueue {

    /**
     * 头节点，存储整个链表的元素，可以从头节点遍历整个链表
     */
    private MyNode head;
    /**
     * 尾节点，存储单独的尾节点
     */
    private MyNode tail;
    /**
     * 队列元素个数
     */
    private int size;


    private static class MyNode{

        String item;

        MyNode next;

        public MyNode(String item){
            this.item = item;
        }

    }

    /**
     * 入队：添加尾节点
     */
    public boolean offer(String e){
        MyNode newNode = new MyNode(e);
        //如果队列为空
        if(isEmpty()){
            //头节点、尾节点 指向同一个节点
            head = tail = newNode;
        }else{
            //将新节点作为尾节点的下个节点
            //由于这尾节点与头结点的内存地址是一致的，修改尾节点，则也是修改头节点
            tail.next = newNode;
            //新节点作为尾节点
            tail = newNode;
        }
        size++;
        return true;
    }

    /**
     * 移除头部节点
     */
    public String poll(){
        //如果队列为空
        if(isEmpty()){
            return null;
        }
        MyNode oldHead =  head;
        //获得头节点的值
        String item = oldHead.item;
        //获得头节点的下个节点，并将下个节点赋值给头节点
        head = oldHead.next;
        //把旧的表头的下一个节点指向设置为null，让gc回收
        oldHead.next = null;
        //队列为空，尾节点也需要置为 null
        if(head == null){
            tail = null;
        }
        size--;
        return item;
    }

    /**
     * 队列是否已空
     */
    public boolean isEmpty(){
        //也可以使用 head == tail
        return size == 0;
    }
    /**
     * 获得队列头部元素，如果队列为空，则返回null
     */
    public Object peek(){
        return isEmpty() ? null : head.item;
    }

    public void print(){
        System.out.print("链表元素：");
        MyNode cur = head;
        while (cur != null){
            System.out.println(cur.item + " ");
            cur = cur.next;
        }
    }

    public static void main(String[] args) {
        MyLinkedListQueue queue = new MyLinkedListQueue();
        System.out.println("获得头元素：" + queue.peek());
        System.out.println("插入元素：" + queue.offer("a"));
        System.out.println("插入元素：" + queue.offer("b"));
        System.out.println("插入元素：" + queue.offer("c"));
        System.out.println("插入元素：" + queue.offer("d"));
        queue.print();
        System.out.println("移除元素：" + queue.poll());
        System.out.println("移除元素：" + queue.poll());
        System.out.println("移除元素：" + queue.poll());
        System.out.println("移除元素：" + queue.poll());
        System.out.println("移除元素：" + queue.poll());
        System.out.println("获得头元素：" + queue.peek());
    }

}
